#ifndef SWORD_TO_OFFER_H
#define SWORD_TO_OFFER_H
#include <iostream>
#include <stack>
bool find(int *matrix, int rows, int columns, int number) {
	if (!matrix || rows < 1 || columns < 1)
		return false;
	bool find = false;
	int ri = 0, ci = columns;
	while (ri < rows && ci > 0) {
		if (matrix[ri * columns + ci - 1] > number) {
			ri++;
			continue;
		}
		if (matrix[ri * columns + ci - 1] < number) {
			ci--;
			continue;
		}
		find = true;
		break;
	}
	return find;
}


void replaceSpace(char *cs, int length) {
	unsigned spaces = 0;
	for (int i = 0; i < length; i++) {
		if (cs[i] == ' ')
			spaces++;
	}
	for (int i = length - 1; i >= 0; i--) {
		if (cs[i] == ' ') {
			--spaces;
			cs[i + spaces * 2] = '%';
			cs[i + 1 + spaces * 2] = '2';
			cs[i + 2 + spaces * 2] = '0';
		}
		else {
			cs[i + spaces * 2] = cs[i];
		}
		if (!spaces)
			break;
	}
}

struct BinaryTreeNode {
	int m_nValues;
	BinaryTreeNode *m_pLeft;
	BinaryTreeNode *m_pRight;
};
BinaryTreeNode *rebuildBinaryTree(int *preOrder, int *inOrder, int length) {
	if (!preOrder || !inOrder || length < 1)
		return nullptr;
	if (length == 1) {
		BinaryTreeNode *root = new BinaryTreeNode();
		root->m_nValues = *preOrder;
		return root;
	}

	BinaryTreeNode *root = new BinaryTreeNode();
	root->m_nValues = *preOrder;
	root->m_pLeft = nullptr;
	root->m_pRight = nullptr;

	int index = 0;
	for (int i = 0; i < length; i++) {
		if (*(inOrder + i) == *preOrder) {
			index = i;
			break;
		}
	}

	if (index == 0) {
		root->m_pRight = rebuildBinaryTree(preOrder + 1, inOrder + 1, length - 1);
	}
	else if (index == length - 1) {
		root->m_pLeft = rebuildBinaryTree(preOrder + 1, inOrder, length - 1);
	}
	else {
		int left = index;
		int right = length - index - 1;
		root->m_pLeft = rebuildBinaryTree(preOrder + 1, inOrder, left);
		root->m_pRight = rebuildBinaryTree(preOrder + 1, inOrder + index + 1, right);
	}
	return root;

}

void testReplaceSpace() {
	char cs[100] = "abcd efg hi jkl ";
	replaceSpace(cs, 16);
	for (int i = 0; i < 50; i++) {
		std::cout << cs[i];
	}
	std::cout << std::endl;
}
void testFindInMatrix() {
	int m[] = { 1,2,3,4,5,6,7,8,9 };
	int number = 10;
	if (find(m, 3, 3, number))
		std::cout << "find " << number << " in the matrix" << std::endl;
	else
		std::cout << "not find " << number << " in the matrix\n";
}

class MaxStack {
public:
	void push(const int &i) {
		if (stack.empty()) {
			stack.push(i);
			maxStack.push(i);
			return;
		}
			

		int top = stack.top();
		stack.push(i);
		if (top > i)
			maxStack.push(top);
		else
			maxStack.push(i);
	}
	int max() {
		return maxStack.top();
	}

	int &top() {
		return stack.top();
	}

	int pop() {
		int top = stack.top();
		stack.pop();
		maxStack.pop();
		return top;
	}
	size_t size() {
		return stack.size();
	}
	bool empty() {
		return stack.empty();
	}
private:
	std::stack<int> stack;
	std::stack<int> maxStack;
};
class Myqueue {
public:
	int max() {
		if (!stack1.empty() && stack2.empty()) {
			return stack1.max();
		}
		if (stack1.empty() && !stack2.empty())
			return stack2.max();
		return stack1.max() > stack2.max() ? stack1.max() : stack2.max();
	}
	void enqueue(int i) {
		stack2.push(i);
	}

	int dequeue() {
		if (stack1.empty()) {
			while (!stack2.empty()) {
				stack1.push(stack2.top());
				stack2.pop();
			}
		}
		if (stack1.empty())
			return 0;
		int r = stack1.top();
		stack1.pop();
		return r;

		
	}
	size_t size() {
		return stack1.size() + stack2.size();
	}
	int empty() {
		return stack1.empty() && stack2.empty();
	}
	int &front() {
		return stack1.top();
	}
private:
	MaxStack stack1;
	MaxStack stack2;
};

void testMyqueue() {
	Myqueue q;
	q.enqueue(1);
	q.enqueue(2);
	q.enqueue(4);
	q.enqueue(3);
	while (!q.empty()) {
		std::cout << q.max() << std::endl;
		q.dequeue();
	}
}

#endif